package com.leetcode.partition5;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/9/4 9:39
 */
public class LC406根据身高重建队列 {

    public static int[][] reconstructQueue(int[][] people) {
        return greedy(people);
    }

    public static void main(String[] args) {
//        int[][] people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};  //{{5, 0}, {7, 0}, {5, 2}, {6, 1}, {4, 4}, {7, 1}}
        //[[9,0],[7,0],[1,9],[3,0],[2,7],[5,3],[6,0],[3,4],[6,2],[5,2]]
        int[][] people = {{9, 0}, {7, 0}, {1, 9}, {3, 0}, {2, 7}, {5, 3}, {6, 0}, {3, 4}, {6, 2}, {5, 2}};

        //[[3,0],[6,0],[7,0],[5,2],[3,4],[5,3],[6,2],[2,7],[9,0],[1,9]]
        Arrays.stream(reconstructQueue(people)).forEach(item -> System.out.println(Arrays.toString(item)));
    }

    private static int[][] greedy(final int[][] people) {
        //将people属性根据hi从高到低排序，如果hi相同，则按照ki升序排列
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);         //{{7, 0}, {7, 1}, {6, 1}, {5, 0}, {5, 2}, {4, 4}}
        List<int[]> listArray = new LinkedList<>();
        //遍历people，根据ki进行指定位置的移动
        for (int i = 0; i < people.length; i++) {
            //将people[ki]到people[i]的元素全部向后移动，people[ki]=people[i]
            listArray.add(people[i][1], people[i]);
        }
        return listArray.toArray(new int[listArray.size()][]);
    }
}
